package com.bishi;


import com.chapter1.LRUCache;

import java.util.List;

/**
 * 将给定的单链表重新排序
 */
public class 微盟3 {
    public static void main(String[] args) {

    }

    public void reorderList(ListNode head) {
        if(head==null || head.next==null){
            return;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next !=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode temp = slow.next;
        slow.next = null;
        ListNode pre = null;
        while(temp !=null){
            ListNode dummy = temp.next;
            temp.next=pre;
            pre=temp;
            temp=dummy;
        }
        ListNode fir = head;
        ListNode sec = pre;
        while(fir!=null&&sec!=null){
            ListNode firNode = fir.next;
            ListNode secNode = sec.next;
            fir.next=sec;
            sec.next=fir;
            fir=firNode;
            sec=secNode;
        }
    }


    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
    }
}
